#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
const int N = 10000;
int n;
int p[N];
bool st[N];
int phi[N];
int cnt;
void get_phi()
{
	phi[1] = 1;
	for (int i = 2; i <= n / i; i++)
	{
		if (!st[i])
		{
			p[++cnt] = i;
			phi[i] = i-1;
		}
		for (int j = 1; 1ll * i * p[j] <= n; j++)
		{
			st[i * p[j]] = true;
			int x = i * p[j];
			if (i % p[j] == 0)
			{
				phi[x] = phi[i] * p[j];
				break;
			}
			else
			{
				phi[x] = phi[i] * (p[j] - 1);
			}
		}
	}
}